package A_sort;

/**
 * 1 * @Author: Eric Tian
 * 2 * @Description: 堆排序
 */
public class F_HeapSort {
    public static void heapSort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        for (int i = 0; i < arr.length; i++) {//O(N)
            heapInsert(arr,i);//O(logN)
        }
        int heapSize = arr.length;
        Swap.swap(arr,0,--heapSize);
        while (heapSize>0){//O(N)
            heapify(arr,0,heapSize);//O(logN)
            Swap.swap(arr,0,--heapSize);//O(1)
        }
    }

    //某个数现在处于index位置，向上进行移动
    public static void heapInsert(int[] arr , int index){
        while (arr[index]>arr[(index-1)>>1]){
            Swap.swap(arr,index,(index-1>>1));
        }
    }

    //某个数出处于index位置，向下进行移动
    public static void heapify(int[]arr ,int index,int heapSize){
        int left= index<<1+1;//左孩子下标
        while (left<heapSize){//下方还有孩子的时候
            //两个孩子谁大小标给largest
            int largest = left+1 < heapSize && arr[left+1]>arr[left] ? left+1 : left;
            //父和孩子之间，谁的值大，把下标给largest
            largest = arr[largest]>arr[index] ?largest:index;
            if (largest == index){
                break;
            }
            Swap.swap(arr,largest,index);
            index = largest;
            left = index<<1+1;
        }
    }

}
